/*
 * Copyright (c) Huawei Technologies Co., Ltd. 2020-2020. All rights reserved.
 * Description: LCG(Linear Congruential Generator) is an algorithm
 * that yields a sequence pseudo-randomized numbers calculated with
 * a discontinuous piecewise linear equation.
 * The generator is defined by recurrence relation:
 * X(i+1) = (a * X(i) + c) (mod m), i >= 0 && i < n
 * The "X(0...n-1)" is just the "lcg96_rand[]" array.
 * Author: luohaizheng
 * Create: 2020-07-20
 */
#include <linux/types.h>
#include <linux/kernel.h>

#define LCG96_RAND_NUM  7
#define U32_BITS        32
#define LCG96_OFFSET    5
#define LCG96_XI_NUM    2

enum {
	LCG96_U32_LOW = 0,
	LCG96_U32_MID = 1,
	LCG96_U32_HIG = 2,
	LCG96_U32_NUM = 3
};

static void lcg96_calc(const u32 *x0, const int x0_len, u32 *x1,
		       const int x1_len)
{
	int i, j, k, h;
	u32 t_x[LCG96_U32_NUM] = { 0 };
	u64 tmp, carry;

	/* The multiplier, its value is 5^41 which divided into 3 parts */
	const u32 multiplier[LCG96_U32_NUM] = {
		0x5aa1cae5,
		0xd0cf37be,
		0x92efd1b8
	};

	for (i = 0; i < x1_len; i++)
		x1[i] = 0;
	x1[0] = 1;

	for (i = 0; i < x0_len; i++) {
		for (j = 0; j < x1_len && (i + j) < x1_len; j++) {
			tmp = (u64)multiplier[i] * (u64)x0[j];
			t_x[1] = (u32)(tmp >> U32_BITS);
			t_x[0] = (u32)tmp;
			carry = 0ull;
			for (k = i + j; k < x1_len; k++) {
				h = k - (i + j);
				tmp = (u64)(x1[k] + t_x[h] + carry);
				carry = (tmp > UINT_MAX) ? 1ull : 0ull;
				x1[k] = (u32)tmp;
			}
		}
	}
}

u32 random_get(u32 seed)
{
	int i, j, k = 1;
	int h = (k + LCG96_OFFSET) % LCG96_RAND_NUM;
	u64 lcg96_rand[LCG96_RAND_NUM];
	u32 x_i[LCG96_XI_NUM][LCG96_U32_NUM];

	for (i = 0; i < LCG96_XI_NUM; i++) {
		for (j = LCG96_U32_LOW; j < LCG96_U32_NUM; j++)
			x_i[i][j] = 0;
	}
	x_i[0][LCG96_U32_LOW] = seed;
	j = 0;
	for (i = 0; i < LCG96_RAND_NUM; i++) {
		lcg96_calc(x_i[j], LCG96_U32_NUM, x_i[1 - j], LCG96_U32_NUM);
		j = 1 - j;
		/* Take bits 95...32 of "Xi[]" as lcg96_rand numbers */
		lcg96_rand[i] =
			(u64)x_i[j][LCG96_U32_HIG] |
			((u64)x_i[j][LCG96_U32_MID] << U32_BITS);
	}
	/* make sure lcg96_rand contains at least one odd number */
	lcg96_rand[0] |= 1ull;
	lcg96_rand[h] += lcg96_rand[k];

	return (u32)lcg96_rand[h];
}
